package sliding_window;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Description 209. 长度最小的子数组
 * @Author Firenut
 * @Date 2023-01-17 22:51
 */
public class T209_minSubArrayLen {
    @Test
    public void test() {
//        int[] nums = {2, 3, 1, 2, 4, 3};
//        int target = 7;

//        int target = 4;
//        int[] nums = {1, 4, 4};
        int target = 15;
        int[] nums = {1, 2, 3, 4, 5};
        minSubArrayLen2(target, nums);
    }

    @Test
    public void test2() {
        int[] nums = {2, 5, 7, 10, 15, 18, 20};
        int target = 9;
        int i = Arrays.binarySearch(nums, target);
        System.out.println(i);
    }

    // 法1: 滑动窗口
    // 时间复杂度: O(n)
    public int minSubArrayLen(int target, int[] nums) {
        int left, right;    //左右指针
        left = right = 0;
        int sum = nums[left];
//        int min = nums.length;  //记录最小长度
        int min = Integer.MAX_VALUE;  //记录最小长度

        if (nums.length == 0) {
            return 0;
        }

        while (true) {
            while (sum < target) {
                right++;
                if (right < nums.length) {
                    sum += nums[right];
                } else { //如果right已经超出右边界了，就表示算法结束了，没必要移动左指针
                    //有两种情况
                    if (left == 0) {    //left一直没有移动,说明整个数组加起来的和都没有达到target
                        return 0;
                    }
                    else {  //left不为0,说明至少存在一种方案
                        return min;
                    }
                }
            }
            while (sum >= target) {
                min = Math.min(min, right - left + 1);
                sum -= nums[left];
                left++;
            }
            if (left >= nums.length - 1) {
                break;
            }
        }
        return min;
    }

    // 基于上面做了点小调整
    public int minSubArrayLen1(int target, int[] nums) {
        int left, right;    //左右指针
        left = right = 0;
        int sum = nums[left];
//        int min = nums.length;  //记录最小长度
        int min = Integer.MAX_VALUE;  //记录最小长度

        if (nums.length == 0) {
            return 0;
        }

        while (true) {
            while (sum < target) {
                right++;
                if (right < nums.length) {
                    sum += nums[right];
                } else { //如果right已经超出右边界了，就表示算法结束了，没必要移动左指针
                    return min == Integer.MAX_VALUE ? 0 : min;
                }
            }
            while (sum >= target) {
                min = Math.min(min, right - left + 1);
                sum -= nums[left];
                left++;
            }
            if (left >= nums.length - 1) {
                break;
            }
        }
        return min;
    }

    // 法2 前缀和+二分查找
    // 时间复杂度: O(n*logn)
    public int minSubArrayLen2(int target, int[] nums) {
        int[] sums = new int[nums.length+1]; //前缀和数组(nums数组的元素是递增的,所以累加之后肯定是递增的)
        // 数组长度len+1是为了让sum[0]=0,这样如果加上target，如果越界，说明整个前缀和都没有找到,没有越界说明存在
        // (比如:target={1 2 3 4 5},target=15;如果让sum[0]=1,那么后面二分查找的下标显然是越界的,没法找到)
//        sums[0] = nums[0]; error
        int min=Integer.MAX_VALUE;
        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i-1];
        }

//        System.out.println(Arrays.toString(sums));

        for (int i = 0; i < nums.length + 1; i++) {
            //这里要写 len+1,虽然nums数组最大下标是len-1;而sums数组最大下标是len
            int s = sums[i] + target;
            // sums[index]-sums[i] >= target <====>  sums[index] >= sums[i]+target
            // 所以你直接按照 sums[i]+target去求得的sums[index]必定满足 >= sums[i]+target,只是需要判断index是否越界、sums[index]这个元素是否存在于sums数组中
            // 如果index<0,说明没找到,取反后如果没有越界，说明相应位置的sums[index]满足sums[index] > sums[i]+target，是合法的
            // 如果index < nums.length + 1,说明找到了sums[index]满足sums[index] == sums[i]+target，合法
            // 如果index >= nums.length + 1,说明越界了,不合法
            int index = Arrays.binarySearch(sums, s);
            if (index < 0) {
                index = ~index;
            }
            if (index < nums.length + 1) {
                min = Math.min(min, index - i);
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}